#coding: utf-8
from __future__ import division
from math import sqrt


#user based

def sim_distance(prefs, person1, person2):
    si = {}
    for item in prefs[person1]:
        if item in prefs[person2]:
            si[item] = 1
    
    if len(si) == 0: return 0
    
    sum_of_squares = sum([ pow(prefs[person1][item]-prefs[person2][item],2) \
                          for item in prefs[person1] if item in prefs[person2] ])
    
    return 1.0/(1+sum_of_squares)
    
def sim_pearson(prefs, person1, person2):
    '''
    对归一化处理的不太好的情况下试用，例如某些人的会比较苛刻。
    好像这个算法实现的有些问题
    '''
    #print '*'*30
    
    si = {}
    for item in prefs[person1]:
        if item in prefs[person2]:
            si[item] = 1
            
    n = len(si)
    
    #print 'calc sim of %s and %s ... (%d)'%(person1.username, person2.username, n)
    if n==0: return 0
    
    sum1, sum2, sum1Sq, sum2Sq, pSum = 0.0, 0.0, 0.0, 0.0, 0.0
    
    for it in si:
        sum1 += prefs[person1][it]
        sum2 += prefs[person2][it]
        sum1Sq += prefs[person1][it] * prefs[person1][it]
        sum2Sq += prefs[person2][it] * prefs[person2][it]
        pSum += prefs[person1][it] * prefs[person2][it]
    
    #print sum1, sum2, sum1Sq, sum2Sq, pSum
            
    '''
    sum1, sum2, sum1Sq, sum2Sq, pSum = 0.0, 0.0, 0.0, 0.0, 0.0
    
    sum1 = sum([ prefs[person1][it] for it in si ])
    sum2 = sum([ prefs[person2][it] for it in si ])    
    sum1Sq = sum([pow(prefs[person1][it], 2) for it in si])
    sum2Sq = sum([pow(prefs[person2][it], 2) for it in si])    
    pSum = sum([prefs[person1][it]*prefs[person2][it] for it in si])
    
    #print sum1, sum2, sum1Sq, sum2Sq, pSum
    '''
    
    num = pSum - (sum1*sum2/n)
    #print pSum , sum1, sum2, n
    den = sqrt((sum1Sq-pow(sum1,2)/n) * (sum2Sq-pow(sum2,2)/n))
    #print person1, person2, num ,den
    
    if den==0: return 0.0

    r = num/den   
    
    return r
    #return abs(r)
    
def sim_tanamoto(prefs, person1, person2):
    items1 = prefs[person1]
    items2 = prefs[person2]
    shr = 0
    for item in items1:
        if item in item2:
            shr += 1
    return float(shr)/(len(items1)+len(items2)-shr)

def topMatches(prefs, person, n=5, similarity=sim_distance):
    '''
    寻找品味最接近的人
    '''
    if person not in prefs:
        return None
    
    scores = [(similarity(prefs, person, other),other) \
        for other in prefs if other!=person]
    
    scores.sort()
    scores.reverse()
    return scores[0:n]
    
def getRecommendations(prefs, person, similarity=sim_distance):
    '''
    用来给指定的用户推荐物品
    '''
    totals = {}
    simSums = {}
    for other in prefs:
        if other==person: continue
        sim = similarity(prefs, person, other)
        
        if sim <= 0: continue
        for item in prefs[other]:
            
            if item not in prefs[person] or prefs[person][item] == 0:
                totals.setdefault(item, 0)
                totals[item] += prefs[other][item] * sim
                simSums.setdefault(item, 0)
                simSums[item] += sim
            
    rankings = [(total/simSums[item], item) for item,total in totals.items()]
    
    rankings.sort()
    rankings.reverse()
    return rankings

def transformPrefs(prefs):
    '''
    对prefs字典进行转换，可以用来计算物品间的相似度，在未收集用户信息时可以向用户推荐物品(topMatches)，
    或者发现潜在的客户(getRecommendations)
    '''
    result = {}
    for person in prefs:
        for item in prefs[person]:
            result.setdefault(item, {})            
            result[item][person] = prefs[person][item]
        
    return result
    
#item based
#1.user based的方法对于大的数据集不适用，需要对每个用户和物品进行比较。
#2对于物品很多的情况，不同用户选择的物品的重叠率比较低，而有同样物品是user based相似度计算的基础。
#对于这种物品相对用户多的稀疏数据集，使用item based的效果会更好。
#3.user based也可以先计算前几名相似的用户来做一些优化

def calculateSimilarItems(prefs, n=10, similarity=sim_distance):
    result = {}
    
    itemPrefs = transformPrefs(prefs)
    c = 0
    for item in itemPrefs:
        #c = c + 1
        #if c%100 == 0: print "%d /%d" % (c, len(itemPrefs))
        scores = topMatches(itemPrefs, item, n, similarity)
        result[item] = scores
    #print result
    return result

def getRecommendedItems(prefs, itemMatch, user):
    if prefs == {}:
        return {}
    userRatings = prefs[user]
    scores = {}
    totalSim = {}
    
    for (item,rating) in userRatings.items():
        for (similarity, item2) in itemMatch[item]:
            if item2 in userRatings: continue
            
            scores.setdefault(item2, 0)
            scores[item2] += similarity*rating
        
            totalSim.setdefault(item2, 0)
            totalSim[item2] += similarity
        
    rankings = [ (score/totalSim[item], item) for item,score in scores.items() if totalSim[item]!=0 ]
    rankings.sort()
    rankings.reverse()
    #print rankings
    return rankings